package OptimalAlgorithm.PrefixSum;

import java.util.HashMap;

//给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。
//eg:
//输入：nums = [4,5,0,-2,-3,1], k = 5
//输出：7
//解释：
//有 7 个子数组满足其元素之和可被 k = 5 整除：
//[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
public class SubarraysDivByK {
    public int subarraysDivByK(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0 % k,1);
        int sum = 0;
        int ret = 0;
        //因为要(sum - x) % k == 0，所以将问题转换成在[0,i - 1]中找sum % k = x % k（同余定理） 的x的个数
        for (int i = 0; i < nums.length; i++) {
            sum +=nums[i];//求前缀和
            int r = (sum % k + k) % k;//求前缀和的余数
            ret += map.getOrDefault(r,0);//更新结果
            map.put(r,map.getOrDefault(r,0) + 1);//将i位置的前缀和余数放入map中
        }
        return ret;
    }
}